package 动态规划;


public class Ch08_01背包问题递归 {
    public static void main(String[] args) {
        int[] w={71,69,1};   //重量
        int[] c={100,1,2}; //价值
        int capacity=70;    //背包容量
        System.out.println(maxKnapsack(w,c,capacity));
    }

    public static int maxKnapsack(int[] w,int[] c,int capacity){
        if (capacity<=0){
            return 0;
        }
        int[] select=new int[w.length];
        for (int i = 0; i < w.length; i++) {
            if (c[i]==0){
                continue;
            }
            if (capacity>=w[i]){
                int currVal=c[i];
                c[i]=0;
                select[i]=maxKnapsack(w,c,capacity-w[i]) + currVal;
                c[i]=currVal;
            }
        }
        int max=max(select);
        return max;
    }
    public static int max(int[] nums){
        if (nums==null||nums.length==0){
            return 0;
        }
        int max=0;
        for (int num : nums) {
            if (num>max){
                max=num;
            }
        }
        return max;
    }
}
